import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 给你一个由 n 个整数组成的数组 nums ，和一个目标值 target 。请你找出并返回满足下述全部条件且不重复的四元组 [nums[a], nums[b], nums[c], nums[d]] （若两个四元组元素一一对应，则认为两个四元组重复）：
 * <p>
 * 0 <= a, b, c, d < n
 * a、b、c 和 d 互不相同
 * nums[a] + nums[b] + nums[c] + nums[d] == target
 * 你可以按 任意顺序 返回答案 。
 */
public class Solution {

    public static void main(String[] args) {
        System.out.println(fourSum(new int[]{1, 1, 1, 1}, 4));
        System.out.println(fourSum(new int[]{1, 0, -1, 0, -2, 2}, 0));
        System.out.println(fourSum(new int[]{2, 2, 2, 2, 2}, 8));
        System.out.println(fourSum(new int[]{10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 60, 60, 60, 60, 60, 60, 60, 60, 60, 60, 60, 60, 60, 60, 60, 60, 60, 60, 60, 60, 70, 70, 70, 70, 70, 70, 70, 70, 70, 70, 70, 70, 70, 70, 70, 70, 70, 70, 70, 70, 80, 80, 80, 80, 80, 80, 80, 80, 80, 80, 80, 80, 80, 80, 80, 80, 80, 80, 80, 80, 90, 90, 90, 90, 90, 90, 90, 90, 90, 90, 90, 90, 90, 90, 90, 90, 90, 90, 90, 90}, 200));
    }

    public static List<List<Integer>> fourSum(int[] nums, int target) {
        List<List<Integer>> result = new ArrayList<>();

        if (nums.length < 4) {
            return result;
        }

        Arrays.sort(nums);
        nums = left4(nums);

        int size = nums.length;
        Node root = new Node(0, (short) 0);

        for (int a = 0; a < size; a++) {
            for (int b = a + 1; b < size; b++) {
                for (int c = b + 1; c < size; c++) {
                    for (int d = c + 1; d < size; d++) {
                        if ((nums[a] + nums[b] + nums[c] + nums[d]) == target) {
                            root.add(nums[a], nums[b], nums[c], nums[d]);
//                            result.add(new ArrayList<>(Arrays.asList(nums[a], nums[b], nums[c], nums[d])));
                        }
                    }
                }
            }
        }

        /*
        //去重
        int cur = 0;
        while (cur < result.size()) {
            for (int i = result.size() - 1; i > cur; i--) {
                if (same(result.get(cur), result.get(i))) {
                    result.remove(i);
                }
            }
            cur++;
        }

         */

        return root.toList();
    }

    private static boolean same(List<Integer> left, List<Integer> right) {
        for (int i = 0; i < 3; i++) {
            if (!left.get(i).equals(right.get(i))) {
                return false;
            }
        }
        return true;
    }

    private static int[] left4(int[] arr) {
        int storage = 0;
        int pre = arr[0] - 1;
        int same = 0;
        for (int i = 0; i < arr.length; i++) {
            int cur = arr[i];
            if (cur == pre) {
                same++;
                if (same < 4) {
                    arr[storage] = cur;
                    storage++;
                }
            } else {
                arr[storage] = cur;
                storage++;
                pre = cur;
                same = 0;
            }
        }

        return Arrays.copyOf(arr, storage);
    }

    private static class Node {

        private int num;
        private short level;
        List<Node> sonList;

        Node(int num, short l) {
            this.num = num;
            this.level = l;
            if (l < 4) {
                sonList = new ArrayList<>();
            }
        }

        private void add(int a, int b, int c, int d) {
            for (Node son : sonList) {
                if (son.num == a) {
                    son.add(b, c, d);
                    return;
                }
            }
            Node n = new Node(a, (short) (level + 1));
            n.add(b, c, d);
            sonList.add(n);
        }

        private void add(int a, int b, int c) {
            for (Node son : sonList) {
                if (son.num == a) {
                    son.add(b, c);
                    return;
                }
            }
            Node n = new Node(a, (short) (level + 1));
            n.add(b, c);
            sonList.add(n);
        }

        private void add(int a, int b) {
            for (Node son : sonList) {
                if (son.num == a) {
                    son.add(b);
                    return;
                }
            }
            Node n = new Node(a, (short) (level + 1));
            n.add(b);
            sonList.add(n);
        }

        private void add(int a) {
            for (Node son : sonList) {
                if (son.num == a) {
                    return;
                }
            }
            Node n = new Node(a, (short) (level + 1));
            sonList.add(n);
        }

        private List<List<Integer>> toList() {
            List<List<Integer>> result = new ArrayList<>();
            for (Node n : sonList) {
                n.collect(result);
            }
            return result;
        }

        private void collect(List<List<Integer>> result) {
            for (Node n : sonList) {
                n.collect(result, this.num);
            }
        }

        private void collect(List<List<Integer>> result, int a) {
            for (Node n : sonList) {
                n.collect(result, a, this.num);
            }
        }

        private void collect(List<List<Integer>> result, int a, int b) {
            for (Node n : sonList) {
                result.add(new ArrayList<>(Arrays.asList(a, b, this.num, n.num)));
            }
        }

    }

}